\documentclass[E:/GsjzTle/main/main.tex]{subfiles}


\begin{document}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  插入 \(x\) 数（\(insert(x)\)）
\item
  删除 \(x\) 数(若有多个相同的数，因只删除一个)（\(remove(x)\)）
\item
  查询 \(x\) 数的排名(排名定义为比当前数小的数的个数 \(+1\)
  )（\(x\_rank(x)\)）
\item
  查询排名为 \(x\) 的数（\(rank\_x(x)\)）
\item
  求 \(x\) 的前驱(前驱定义为小于 \(x\)，且最大的数)（\(x\_pre(x)\)）
\item
  求 \(x\) 的后继(后继定义为大于 \(x\)，且最小的数)（\(x\_suf(x)\)）
\end{enumerate}

\begin{lstlisting}
const int N = 2e5 + 10;
int ch[N][2], par[N], val[N], cnt[N], size[N], ncnt, root;
bool chk(int x){
	return ch[par[x]][1] == x;
}
void pushup(int x){
	size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
}
void rotate(int x)
{
	int y = par[x], z = par[y], k = chk(x), w = ch[x][k^1];
	ch[y][k] = w , par[w] = y;
	ch[z][chk(y)] = x , par[x] = z;
	ch[x][k^1] = y , par[y] = x;
	pushup(y) , pushup(x);
}
void splay(int x, int goal = 0)
{
	while (par[x] != goal)
	{
		int y = par[x], z = par[y];
		if (z != goal)
		{
			if (chk(x) == chk(y)) rotate(y);
			else rotate(x);
		}
		rotate(x);
	}
	if (!goal) root = x;
}
void insert(int x)
{
	int cur = root, p = 0;
	while (cur && val[cur] != x)
	{
		p = cur;
		cur = ch[cur][x > val[cur]];
	}
	if (cur) cnt[cur] ++;
	else
	{
		cur = ++ ncnt;
		if (p) ch[p][x > val[p]] = cur;
		ch[cur][0] = ch[cur][1] = 0;
		par[cur] = p;
		val[cur] = x;
		cnt[cur] = size[cur] = 1;
	}
	splay(cur);
}
void find(int x)
{
	int cur = root;
	while (ch[cur][x > val[cur]] && x != val[cur])
	{
		cur = ch[cur][x > val[cur]];
	}
	splay(cur);
}
int kth(int k)
{
	int cur = root;
	while (1)
	{
		if (ch[cur][0] && k <= size[ch[cur][0]])
		{
			cur = ch[cur][0];
		}
		else if (k > size[ch[cur][0]] + cnt[cur])
		{
			k -= size[ch[cur][0]] + cnt[cur];
			cur = ch[cur][1];
		}
		else return cur;
	}
}
int pre(int x)
{
	find(x);
	if (val[root] < x) return root;
	int cur = ch[root][0];
	while (ch[cur][1]) cur = ch[cur][1];
	return cur;
}
int suf(int x)
{
	find(x);
	if (val[root] > x) return root;
	int cur = ch[root][1];
	while (ch[cur][0]) cur = ch[cur][0];
	return cur;
}
void remove(int x)
{
	int last = pre(x), next = suf(x);
	splay(last);
	splay(next, last);
	int del = ch[next][0];
	if (cnt[del] > 1)
	{
		cnt[del]--;
		splay(del);
	}
	else ch[next][0] = 0, pushup(next), pushup(root);
}
int x_rank(int x){
	find(x);
	return size[ch[root][0]];
}
int rank_x(int x){
	return val[kth(x+1)];
}
int x_pre(int x){
	return val[pre(x)];
}
int x_suf(int x){
	return val[suf(x)];
}
int m, op, x;
signed main()
{
	cin >> m;
	insert(0x3f3f3f3f);
	insert(0xcfcfcfcf);
	while(m --)
	{
		cin >> op >> x;
		switch (op)
		{
			case 1:
			insert(x);
			break;
			case 2:
			remove(x);
			break;
			case 3:
			cout << x_rank(x) << '\n';
			break;
			case 4:
			cout << rank_x(x) << '\n';
			break;
			case 5:
			cout << x_pre(x) << '\n';
			break;
			case 6:
			cout << x_suf(x) << '\n';
			break;
		}
	}
	return 0;
}
\end{lstlisting}

\end{document}
